package com.leetcode.partition13;

import java.io.*;

/**
 * 字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
 * 每个元音 'a' 后面都只能跟着 'e'
 * 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
 * 每个元音 'i' 后面 不能 再跟着另一个 'i'
 * 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
 * 每个元音 'u' 后面只能跟着 'a'
 * @author `RKC`
 * @date 2022/1/17 15:13
 */
public class LC1220统计元音字母序列的数目 {

    private static final int N = (int) (2e4 + 10), MOD = (int) (1e9 + 7);
    //dp[0][j]表示以元音'a'开头的总长度是j的满足条件的方案数，dp[1][j]、dp[2][j]、dp[3][j]、dp[4][j]分别对应'e'、'i'、'o'、'u'
    private static int[][] dp = new int[5][N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        writer.write(countVowelPermutation(n) + "\n");
        writer.flush();
    }

    public static int countVowelPermutation(int n) {
        int answer = 0;
        //长度为1的元音字母组成的单词，满足条件的都只有1
        for (int i = 0; i < dp.length; i++) dp[i][1] = 1;
        //'a'后面只能跟'e'：dp[0][j] += dp[1][j - 1]
        //'e'后面只能跟'a'或者'i'：dp[1][j] += dp[0][j - 1] + dp[2][j - 1]
        //'i'后面只要不跟着'i'：dp[2][j] += dp[0][j - 1] + dp[1][j - 1] + dp[3][j - 1] + dp[4][j - 1]
        //'o'后面只能跟着'i'或者'u'：dp[3][j] += dp[2][j - 1] + dp[4][j - 1]
        //'u'后面只能跟着'a'：dp[4][j] = dp[0][j - 1]
        for (int j = 2; j <= n; j++) {
            dp[0][j] = add(dp[0][j], dp[1][j - 1]);
            dp[1][j] = add(dp[1][j], dp[0][j - 1], dp[2][j - 1]);
            dp[2][j] = add(dp[2][j], dp[0][j - 1], dp[1][j - 1], dp[3][j - 1], dp[4][j - 1]);
            dp[3][j] = add(dp[3][j], dp[2][j - 1], dp[4][j - 1]);
            dp[4][j] = dp[0][j - 1];
        }
        for (int i = 0; i < dp.length; i++) answer = add(answer, dp[i][n]);
        return answer;
    }

    private static int add(int... nums) {
        int res = 0;
        for (int num : nums) res = (res + num) % MOD;
        return res;
    }
}
